package leetcode.linked;

public class Solution链表中倒数第k个节点 {
//    给定一个链表: 1->2->3->4->5, 和 k = 2

//    返回链表 4->5


//    方法一：顺序查找
//    以示例为例，链表的长度为 5（即：n），倒数第 2（即：k） 个节点即为 正数 第 3（即：n - k） 个节点，
//    只需要 顺序遍历 到链表的第 3（即：n - k）个节点即为倒数第 2 （即：k）个节点。
    public ListNode method1(ListNode head, int k) {
        int n = 0;

        for (ListNode p = head; p != null; p = p.next) {
            n++;
        }

        ListNode result;
        for (result = head; n > k; n --) {
            result = result.next;
        }
        return result;
    }

    //只需要一次遍历

    //滑动窗口法
    public ListNode method2(ListNode head, int k) {
        ListNode fast = head, slow = head;

        while (fast.next != null && k > 1) {
            fast = fast.next;
            k -- ;
        }

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }

    public ListNode method3(ListNode head, int k) {
        ListNode slow = head;

        for (ListNode fast = head; fast.next != null; fast = fast.next, k --) {
            if (k <= 1) {
                slow = slow.next;
            }
        }

        return k <= 1 ? slow : null;
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(new int[]{1,2,3,4,5,6});

        Solution链表中倒数第k个节点 solution = new Solution链表中倒数第k个节点();

        System.out.println(solution.method1(listNode, 1).val);
        System.out.println(solution.method2(listNode, 1).val);
        System.out.println(solution.method3(listNode, 1).val);
    }
}
